package com.mlh.dp.old;

// 题目：
// 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
// 回文字符串 是正着读和倒过来读一样的字符串。
// 子字符串 是字符串中的由连续字符组成的一个序列。
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
// 举例：输入：s="aaa"
// 输出：6
// 解释：6个回文子串:"a","a","a","aa","aa","aaa"

public class PalindromeSubstrings {

    //这个方法实际上直接用最大回文子串的方法稍作修改就可以了
    //因为最大回文子串其实找出了所有的回文子串  然后比较长度大小
    //而这个问题是找出字符中所有的回文子串  故可以用最大回文子串方法稍作修改即可
    //因此这道题目也可以用马拉车算法，不过需要稍作修改
    public static int method1(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];// boolean默认值是false
        int sLen = s.length();
        int j;// 右边界
        int res=0;
        for (int len = 1; len <=sLen; len++) {
            for (int i = 0; i < sLen; i++) {
                j = i + len - 1;
                if (j >= sLen) {
                    break;// 跳出单层循环
                }
                if ((len == 1 || len == 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j)) {
                    res++;
                    dp[i][j] = true;
                }
            }
        }
        return res;
    }

    //第二种方法：利用遍历回文中心的方式来找到所有的回文子串
    //回文中心 有两种情况   一种是单个字符，另一种是双字符
    public static int method2(String s){
        int res=0;
        for(int i=0;i<s.length();i++){
            res+=expand(s,i,i);//单字符扩展
            if(i+1<s.length()&&s.charAt(i)==s.charAt(i+1)){//双字符扩展，双字符扩展的前提是这个两个字符要先相同
                res+=expand(s,i,i+1);
            }
        }
        return res;
    }
    //扩展方法
    public static int expand(String s, int l, int r) {
        int res = 1;
        for (int i = l; l > 0; --l) {
            if (r < s.length() - 1 && s.charAt(l - 1) == s.charAt(r + 1)) {
                res++;
                r++;
            } else {
                return res;
            }
        }
        return res;
    }
}
